class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m=0,minElem=INT_MAX;
        for(auto x:nums)
        {
            if(x<0)m++;
            minElem=min(minElem,abs(x));
        }
        int ret=0;
        if(m>=k)
        {
            sort(nums.begin(),nums.end());
            for(int i=0;i<k;i++)
            {
                ret+=-nums[i];
            }
            for(int i=k;i<nums.size();i++)
            {
                ret+=nums[i];
            }
        }
        else 
        {
            for(auto x:nums)ret+=abs(x);
            if((k-m)%2)
            {
                ret-=minElem*2;
            }
        }
        return ret;
    }
    
};
